#include <iostream>
using namespace std;

int Partition2(int r[], int low, int high){
    int i=low, j=high, pivot=r[low];
    while(i<j){
        while(i<j && r[j] > pivot) j--;
        while(i<j && r[i] <= pivot) i++;
        if(i<j){
            swap(r[i++], r[j--]);
        }
    }
    if(r[i] > pivot){
        swap(r[i-1], r[low]);
        return i - 1;
    }
    swap(r[i], r[low]);
    return i;
}

void QuickSort2(int R[], int low, int high){
    int mid;
    if(low < high){
        mid=Partition2(R, low, high);
        QuickSort2(R, low, mid-1);
        QuickSort2(R, mid + 1, high);
    }
}

int main(){
    int a[1000];
    int i,N;
    cout<<"请先输入要排序的数据的个数：";
    cin >> N;
    cout<<"请输入要排序的数据：";
    for ( i = 0; i < N; i++){
        cin >> a[i];
    }
    cout<<endl;
    QuickSort2(a, 0, N - 1);
    cout<<"排序后的序列为："<<endl;
    for ( i = 0; i < N; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}
